
package com.nulldev.util.networking.npacket4.iprotocols.ncryptx.methods.sidh;

/**************************************************************************************************
 *
 * Implements elements over finite field GF(p) and the quadratic extension GF(p^2) 
 *  
 **************************************************************************************************/

import java.math.BigInteger;
import java.util.Arrays;
import java.lang.System;
import java.security.SecureRandom;

class InvalidFieldException extends Exception {
	private static final long serialVersionUID = 3424227570372355613L;
}

class Felm {
	/* Elements of GF(p) */

	// Set p to a placeholder value until the prime has been set
	public static BigInteger p = BigInteger.valueOf(2);
	private BigInteger value;
	public static int primesize = 1;

	public static final Felm ZERO = new Felm(BigInteger.ZERO);
	public static final Felm ONE = new Felm(BigInteger.ONE);

	public Felm(BigInteger v) {
		value = v.mod(p);
	}

	public Felm(Felm a) {
		value = a.fpGetValue();
	}

	public Felm(long v) {
		value = BigInteger.valueOf(v).mod(p);
	}

	public Felm(byte[] bytes) {
		value = new BigInteger(bytes);
	}

	public Felm(SecureRandom rnd) {
		value = genRandom(p);
	}

	public static void setPrime(BigInteger pr) throws InvalidFieldException {
		if (pr.isProbablePrime(10))
			p = pr;
		else
			throw new InvalidFieldException();

		primesize = (pr.bitLength() / 8) + 1;
	}

	public static BigInteger getPrime() {
		return p;
	}

	public BigInteger fpGetValue() {
		return value;
	}

	public static BigInteger genRandom(BigInteger bound) {
		// Gen random values up to the same bit length as the bound until the value
		// generated is
		// strictly less than the bound. Average expected number of calls is less than
		// 2.

		SecureRandom rnd = new SecureRandom();
		int numBits = bound.bitLength();

		BigInteger randval = new BigInteger(numBits, rnd);

		while (randval.compareTo(bound) >= 0)
			randval = new BigInteger(numBits, rnd);

		return randval;
	}

	public void randomize() {
		value = genRandom(p);
	}

	public static Felm add(Felm x, Felm y) {
		Felm z = new Felm(x);
		z.fpAddInPlace(y);
		return z;
	}

	public void fpAddInPlace(Felm y) {
		value = value.add(y.value);
		value = value.mod(p);
	}

	public static Felm sub(Felm x, Felm y) {
		Felm z = new Felm(x);
		z.fpSubInPlace(y);
		return z;
	}

	public void fpSubInPlace(Felm y) {
		value = value.add(p).subtract(y.value);
		value = value.mod(p);
	}

	public static Felm mult(Felm x, Felm y) {
		Felm z = new Felm(x);
		z.fpMultInPlace(y);
		return z;
	}

	public void fpMultInPlace(Felm y) {
		value = value.multiply(y.value);
		value = value.mod(p);
	}

	public static Felm sqr(Felm x) {
		return mult(x, x);
	}

	public void fpSqrInPlace() {
		fpMultInPlace(this);
	}

	public boolean fpIsZero() {
		return value.equals(BigInteger.ZERO);
	}

	public boolean fpIsEven() {
		BigInteger c = value.and(BigInteger.ONE);
		return c.equals(BigInteger.ZERO);
	}

	public boolean fpIsOdd() {
		return !fpIsEven();
	}

	public boolean fpEquals(Felm y) {
		return value.equals(y.value);
	}

	public boolean fpIsLessThan(Felm y) {
		return value.compareTo(y.value) == -1;
	}

	public boolean fpIsGreaterThan(Felm y) {
		return value.compareTo(y.value) == 1;
	}

	public static Felm negate(Felm x) {
		return new Felm(p.subtract(x.value));
	}

	public void fpNegateInPlace() {
		value = p.subtract(value);
	}

	public static Felm inverse(Felm x) {
		Felm z = new Felm(x);
		z.fpInverseInPlace();
		return z;
	}

	public void fpInverseInPlace() {
		value = value.modInverse(p);
	}

	public static Felm div2(Felm x) {
		Felm z = new Felm(x);
		z.fpDiv2InPlace();
		return z;
	}

	public void fpDiv2InPlace() {
		if (fpIsOdd())
			value = value.add(p);
		value = value.shiftRight(1);
	}

	public static Felm leftShift(Felm x, int shiftBy) {
		Felm z = new Felm(x);
		z.fpLeftShiftInPlace(shiftBy);
		return z;
	}

	public void fpLeftShiftInPlace(int shiftBy) {
		value = value.shiftLeft(shiftBy);
	}

	public static Felm rightShift(Felm x, int shiftBy) {
		Felm z = new Felm(x);
		z.fpRightShiftInPlace(shiftBy);
		return z;
	}

	public void fpRightShiftInPlace(int shiftBy) {
		value = value.shiftRight(shiftBy);
	}

	public Felm fpSwap(Felm y, BigInteger option) {
		// Constant time swap regardless of whether option is 0 or 1
		BigInteger temp, mask, yval;

		yval = y.value;
		mask = option.negate(); // option = 1 => mask = 1...1 because BigInteger
								// automatically sign extends as necessary

		temp = mask.and(value.xor(yval)); // temp = mask & (this.value xor y.value)
		value = temp.xor(value);
		yval = temp.xor(yval);

		return new Felm(yval);
	}

	public String toString() {
		return "0x" + value.toString(16);
	}

	public byte[] toByteArray() {
		// Returns the same size array regardless of the value. Zero pad the highbits.
		byte[] retval = new byte[primesize];
		Arrays.fill(retval, (byte) 0);

		int eltsize = (value.bitLength() / 8) + 1;
		int offset = primesize - eltsize;

		System.arraycopy(value.toByteArray(), 0, retval, offset, eltsize);

		return retval;
	}
}

class F2elm {
	/* Elements of the quadratic extension field GF(p^2): x0 + x1*i */

	private Felm x0;
	private Felm x1;

	public static final F2elm ZERO = new F2elm(Felm.ZERO, Felm.ZERO);
	public static final F2elm ONE = new F2elm(Felm.ONE, Felm.ZERO);

	public F2elm(BigInteger a0, BigInteger a1) {
		x0 = new Felm(a0);
		x1 = new Felm(a1);
	}

	public F2elm(Felm a0, Felm a1) {
		x0 = new Felm(a0);
		x1 = new Felm(a1);
	}

	public F2elm(F2elm a) {
		x0 = new Felm(a.x0);
		x1 = new Felm(a.x1);
	}

	public F2elm(long v0, long v1) {
		x0 = new Felm(v0);
		x1 = new Felm(v1);
	}

	public F2elm(byte[] bytes) {
		int len = (bytes.length) / 2;
		x0 = new Felm(Arrays.copyOfRange(bytes, 0, len));
		x1 = new Felm(Arrays.copyOfRange(bytes, len, 2 * len));
	}

	public F2elm(SecureRandom rnd) {
		x0 = new Felm(rnd);
		x1 = new Felm(rnd);
	}

	public Felm f2Get0() {
		return x0;
	}

	public Felm f2Get1() {
		return x1;
	}

	public boolean f2Equals(F2elm y) {
		return x0.fpEquals(y.x0) && x1.fpEquals(y.x1);
	}

	public static F2elm add(F2elm x, F2elm y) {
		F2elm z = new F2elm(x);
		z.f2AddInPlace(y);
		return z;
	}

	public void f2AddInPlace(F2elm y) {
		x0.fpAddInPlace(y.x0);
		x1.fpAddInPlace(y.x1);
	}

	public static F2elm sub(F2elm x, F2elm y) {
		F2elm z = new F2elm(x);
		z.f2SubInPlace(y);
		return z;
	}

	public void f2SubInPlace(F2elm y) {
		x0.fpSubInPlace(y.x0);
		x1.fpSubInPlace(y.x1);
	}

	public static F2elm negate(F2elm x) {
		F2elm y = new F2elm(x);
		y.f2NegateInPlace();
		return y;
	}

	public void f2NegateInPlace() {
		x0.fpNegateInPlace();
		x1.fpNegateInPlace();
	}

	public static F2elm sqr(F2elm x) {
		F2elm y = new F2elm(x);
		y.f2SqrInPlace();
		return y;
	}

	public void f2SqrInPlace() {
		Felm t1, t2, t3;

		t1 = Felm.add(x0, x1); // t1 = x0 + x1
		t2 = Felm.sub(x0, x1); // t2 = x0 - x1
		t3 = Felm.leftShift(x0, 1); // t3 = 2 * x0

		x0 = Felm.mult(t1, t2); // x0 = (x0+x1)(x0-x1)
		x1.fpMultInPlace(t3); // x1 = 2*x0*x1
	}

	public static F2elm mult(F2elm y, F2elm z) {
		F2elm x = new F2elm(y);
		x.f2MultInPlace(z);
		return x;
	}

	public void f2MultInPlace(F2elm y) {
		// compute c = this * y = (x0 + i*x1) * (y0 + i*y1) = x0y0 - x1y1 + i*(x0y1 +
		// x1y0)
		@SuppressWarnings("unused")
		Felm t1, t2, c0, c1, y0, y1;

		y0 = y.x0;
		y1 = y.x1;

		t1 = Felm.mult(x0, y0);
		t2 = Felm.mult(x1, y1);
		c0 = Felm.sub(t1, t2);

		// Using extra additions, but fewer multiplications
		t1.fpAddInPlace(t2);
		t2 = Felm.add(x0, x1);
		x1 = Felm.add(y0, y1);
		x1.fpMultInPlace(t2);
		x1.fpSubInPlace(t1);
		x0 = c0;
	}

	public static F2elm rightShift(F2elm y, int n) {
		F2elm x = new F2elm(y);
		x.f2RightShiftInPlace(n);
		return x;
	}

	public void f2RightShiftInPlace(int n) {
		x0.fpRightShiftInPlace(n);
		x1.fpRightShiftInPlace(n);
	}

	public static F2elm leftShift(F2elm y, int n) {
		F2elm x = new F2elm(y);
		x.f2LeftShiftInPlace(n);
		return x;
	}

	public void f2LeftShiftInPlace(int n) {
		x0.fpLeftShiftInPlace(n);
		x1.fpLeftShiftInPlace(n);
	}

	public boolean f2IsEven() {
		return x0.fpIsEven() && x1.fpIsEven();
	}

	public static F2elm div2(F2elm y) {
		F2elm x = new F2elm(y);
		x.f2Div2InPlace();
		return x;
	}

	public void f2Div2InPlace() {
		x0.fpDiv2InPlace();
		x1.fpDiv2InPlace();
	}

	public static F2elm inverse(F2elm y) {
		F2elm x = new F2elm(y);
		x.f2InverseInPlace();
		return x;
	}

	public void f2InverseInPlace() {
		Felm t0, t1;

		t0 = Felm.sqr(x0);
		t1 = Felm.sqr(x1);
		t0.fpAddInPlace(t1);
		t0.fpInverseInPlace();
		x1.fpNegateInPlace();
		x0.fpMultInPlace(t0);
		x1.fpMultInPlace(t0);
	}

	public static F2elm[] inv3Way(F2elm z0, F2elm z1, F2elm z2) {
		// Compute simultaneous inversion of 3 elements

		F2elm t0, res[] = new F2elm[3];

		t0 = mult(z0, z1); // t0 = z0*z1
		res[1] = mult(t0, z2); // res1 = z0*z1*z2
		res[2] = inverse(res[1]); // res2 = 1/(z0*z1*z2)
		res[1] = mult(res[2], z2); // res1 = 1/(z0*z1)
		res[0] = mult(res[1], z1); // res0 = 1/z0
		res[1].f2MultInPlace(z0); // res1 = 1/z1
		res[2].f2MultInPlace(t0); // res2 = 1/z2

		return res;
	}

	public static F2elm[] inv4Way(F2elm z0, F2elm z1, F2elm z2, F2elm z3) {
		// Compute simultaneous inversion of 4 elements

		F2elm res[] = new F2elm[4];

		res[0] = mult(z0, z1); // res0 = z0*z1
		res[1] = mult(z2, z3); // res1 = z2*z3
		res[2] = mult(res[0], res[1]); // res2 = z0*z1*z2*z3
		res[3] = inverse(res[2]); // res3 = 1/(z0*z1*z2*z3)
		res[2] = mult(res[1], res[3]); // res2 = 1/(z2*z3)
		res[3].f2MultInPlace(res[0]); // res3 = 1/(z0*z1)
		res[0] = mult(res[2], z1); // res0 = 1/z0
		res[1] = mult(res[2], z0); // res1 = 1/z1
		res[2] = mult(res[3], z3); // res2 = 1/z2
		res[3].f2MultInPlace(z2); // res3 = 1/z3

		return res;
	}

	public F2elm f2Swap(F2elm y, BigInteger option) {
		// Constant time swap regardless of whether option is 0 or 1
		Felm y0, y1;

		y0 = x0.fpSwap(y.x0, option);
		y1 = x1.fpSwap(y.x1, option);

		return new F2elm(y0, y1);
	}

	public static F2elm select(F2elm x, F2elm y, BigInteger option) {
		// Return x if option = 0 and y if option = 1
		BigInteger y0, y1, z0, z1, mask, bix0, bix1;

		mask = option.negate(); // if option = 1 then mask = 1...1 because BigInteger
								// automatically sign extends as necessary

		// Get x0, x1, y0, y1 as their BigInteger representations
		y0 = (y.x0).fpGetValue();
		y1 = (y.x1).fpGetValue();
		bix0 = (x.x0).fpGetValue();
		bix1 = (x.x1).fpGetValue();

		z0 = bix0.xor(y0); // z0 = x0 xor y0
		z1 = bix1.xor(y1); // z1 = x1 xor y1

		z0 = z0.and(mask); // if mask = 0 then z0 = 0 else z0 = x0 xor y0
		z1 = z1.and(mask); // if mask = 0 then z1 = 0 else z1 = x1 xor y1

		z0 = bix0.xor(z0); // if mask = 0 then z0 = x0
							// else z0 = x0 xor x0 xor y0 = y0

		z1 = bix1.xor(z1); // if mask = 0 then z1 = x1
							// else z1 = x1 xor x1 xor y1 = y1

		return new F2elm(z0, z1);
	}

	public String toString() {
		return "[" + x0 + "," + x1 + "]";
		// return x1 + "*i + " + x0;
	}

	public byte[] toByteArray() {
		byte[] retval = new byte[2 * Felm.primesize];
		System.arraycopy(x0.toByteArray(), 0, retval, 0, Felm.primesize);
		System.arraycopy(x1.toByteArray(), 0, retval, Felm.primesize, Felm.primesize);
		return retval;
	}
}
